from point import *

# TODO: let me say "for pt in board: ..."!  (who would use this?)

# TODO: draw a pretty picture of what self.chains looks like

# TODO: get rid of do_captures() -- insert it into place_stone() inline!

# TODO: add move_number (so you know how far you can undo!) -- nah, obsolete with new gametree...

# ALSO:
# - need undo() function -- it's not *that* hard...
# --- though it's nice to have all the rules in one place, with no extra crap.
# --- possibly even: UndoableBoard(Board), that adds an undo() method?
# - just write an undo() method (no need for redo -- just replay it); possible strategy:
# --- change play/pass slightly:
# --- make copy of board/markers/turn/... (size is const!)
# --- do normal play-stone stuff
# --- compare new-board with old-board; make a BoardDiff from this
# --- (it's a list of (point,color) tuples -- what to do to new_board to make it into old_board)
# --- actually, markers/turn always change, so they're stored as-is
# --- push the BoardDiff onto self.history
# --- if the user calls board.undo(), pop the last BoardDiff, and apply it

# - need to make sure i'm clear on what makes a new move -- markers no, passing yes?
# --- order is: is_*(pt), play/pass, then add all markers for that turn (right?)

# PUBLIC:
# - __init__()
# - reset()
# - mark()
# - set_handicap()
# - get()
# - is_ko()
# - is_legal()
# - play_stone()
# - play_pass()
# - last_stone
# - black_prisoners, white_prisoners
# - turn
# - markers
# PRIVATE:
# - (everything else)
# - size, handicap_stones, ...  (no reason to read)
# - __is_suicide
# - __is_ko_legal
# - __count_liberties
# - __do_captures
# - __kill
# - __rename
# STATE:
# - size, chain, handicap_stones
# - next_chain, turn, black_prisoners, white_prisoners, markers

# (where do these go?  consts.py?)
EMPTY = 0
BLACK = 1
WHITE = 2
def opposite(color):
    if color == BLACK:
        return WHITE
    else:
        return BLACK

# type of a marker is one of these ints, or a string.
MARKER_SQUARE = 1
MARKER_TRIANGLE = 2
MARKER_X = 3
MARKER_CIRCLE = 4
MARKER_WHITE_TERRITORY = 5
MARKER_BLACK_TERRITORY = 6
MARKER_SELECTED = 7 # the spec says just "SL", but ff4_ex.sgf calls it "selected points")
# note that sgf defines markers that don't occupy only one point -- lines, shading, etc.

class Board(object):
    """A go board's position; this also incorporates all of the rules of go.
    (Except scoring, yet.)  To use:

    b = Board() # or b.reset(), if you want to re-use it
    for m in moves: # you have a list of moves, i take it
        b.play_stone(point, color) # or b.play_pass()
    # now you can use b.get(pt) to get whaat's at point pt

    There's no undo (it's hard to implement); if you want to go back
    one, reset the board and replay n-1 moves.

    Use b.is_ko() to find out if the last move was a ko.  You might want to display this differently.

    Use b.is_legal(pt, color) to find out if |pt| is a legal move for |color|.
    """
    def __init__(self, size=19):
        self.size = size
        self.chain = [ [0]*size for x in range(size) ] # 2d array, all 0's
        self.handicap_stones = []

        self.reset()

    def mark(self, point, type):
        self.markers += [ (point, type) ]

    def set_handicap(self, stones):
        # make a copy for later
        self.handicap_stones = stones[:]

        # place them on the board
        self.reset()

    def reset(self):
        for i in range(self.size):
            for j in range(self.size):
                self.chain[i][j] = 0
        self.next_chain = 1

        # place them on the board
        for s in self.handicap_stones:
            self.play_stone(s, BLACK)

        if self.handicap_stones:
            self.turn = WHITE
        else:
            self.turn = BLACK

        self.last_stone = None
        self.last_captures = 0

        self.black_prisoners = self.white_prisoners = 0

        # list of markers, in some format -- for now, try (point,type) tuples
        self.markers = []

    def get(self, pt):
        """get the stone at the specified point (a Point).
        stone must be in bounds!
        """
        chain_id = self.chain[pt.col][pt.row]
        if chain_id == 0:
            return EMPTY
        elif chain_id > 0:
            return BLACK
        else:
            return WHITE

    # was the last stone played, a ko?  we'll call it a ko if it's all by
    # itself (1-stone group), has exactly 1 liberty, and the previous
    # move captured exactly 1 stone.
    def is_ko(self):
        # a pass is not a ko.
        if self.last_stone is None:
            return False

        # if you didn't capture 1 stone, it's not a ko
        if self.last_captures != 1:
            return False

        # strategy: look at the points around it.  count same-color
        # stones, and empty points.  to be a ko, it needs
        # same-color=0, and empty=1.

        my_color = self.get(self.last_stone) # (not a pass, so it has to be BLACK or WHITE)

        # count bordering points with same-color
        same_color = len([pt for pt in self.last_stone.all4(self.size) if self.get(pt)==my_color])

        # count bordering empty points
        empty_point = len([pt for pt in self.last_stone.all4(self.size) if self.get(pt)==EMPTY])

        return (same_color == 0 and empty_point == 1)

    def list_all_legal_moves(self, color):
        return [Point(x,y) for x in range(self.size)
                           for y in range(self.size)
                           if self.is_legal(Point(x,y), color)]

    def is_legal(self, pt, color):
        """is this move legal?  (needs to be empty, not suicide, and not a ko violation.)"""
        return self.get(pt)==EMPTY and \
               (not self.__is_suicide(pt, color)) and \
               self.__is_ko_legal(pt, color)

    def __is_suicide(self, point, color):
        # if any group of my opponent's color touching the new stone
        # has exactly 1 liberty, it's a kill, so it's not a suicide.
        for pt in point.all4(self.size):
            if self.get(pt)==opposite(color) and self.__count_liberties(pt)==1:
                return False

        # else, if this point has liberties, then it's not a suicide.
        if [pt for pt in point.all4(self.size) if self.get(pt) == EMPTY]:
            return False
        # (why isn't this simply a call to count_liberties()?
        # because that's O(n^2), and counts liberties to a *chain*; i want for a *point*!)

        # else, if this stone is touching no stones of its same color,
        # then it is a suicide.
        friends = [pt for pt in point.all4(self.size) if self.get(pt)==color]
        if not friends:
            return True

        # else, if all groups of my own color touching the new stone
        # have exactly 1 liberty, then this stone fills the last
        # liberty, so it's a suicide.

        # (put another way: if any group of my own color touching this
        # one has >1 liberty, it's legal.  otherwise, it's a suicide.)
        for pt in point.all4(self.size):
            if self.get(pt)==color and self.__count_liberties(pt)>1:
                return False

        # else, it's not a suicide.
        return True

    # (japanese ko rule, not chinese superko)
    def __is_ko_legal(self, pt, color):
        # - opponent just captured exactly 1 stone
        # (opposite: if he didn't just capture exactly 1 stone)
        if self.last_captures != 1:
            return True

        # - your move is in the same place as the stone he just captured
        # SIMPLER: if your stone is one step away from his (CHECK: that's right, right?)
        # (opposite: if your stone is not one step away, it's legal)
        if pt not in self.last_stone.all4(self.size):
            return True

        # - the opponent's last stone has 1 liberty and no same-color stones touching it
        # (opposite: last move has either 2+ liberties, or 1+ same-color stones touching it)

        # count the opponent's stone's liberties
        liberties = len([pt for pt in self.last_stone.all4(self.size) if self.get(pt)==EMPTY])

        same_color_neighbors = len([pt for pt in self.last_stone.all4(self.size)
                                    if self.get(pt)==opposite(color)])

        if (liberties >= 2 or same_color_neighbors >= 1):
            return True

        return False

    # count the number of liberties the chain at point |pt| has.
    # (runs in O(size^2) time.)
    # actually, that's a lie: it just figures out if it's 0, 1, or 2 (= more than 1).
    def __count_liberties(self, pt):
        chain_id = self.chain[pt.col][pt.row]

        liberties = 0

        for x in range(self.size):
            for y in range(self.size):
                # this point is a liberty if:
                # - id=0 (empty), and
                # - one of its 4 neighbors has id=id

                # instead of always starting at the top, start 1 stone up from
                # the stone we're interested in.  this is a big time savings.
                # (but i still check everything!)
                xx = (x + pt.col - 1) % self.size
                yy = y # (y + pt.row - 1) % self.size

                if (self.chain[xx][yy] != 0): # (stone here -- not a liberty)
                    continue

                if (xx-1 >= 0 and self.chain[xx-1][yy] == chain_id) or \
                    (xx+1 < self.size and self.chain[xx+1][yy] == chain_id) or \
                    (yy+1 < self.size and self.chain[xx][yy+1] == chain_id) or \
                    (yy-1 >= 0 and self.chain[xx][yy-1] == chain_id):
                    liberties += 1

                # (i don't ever care about the difference between 2,
                # 3, and 4 -- so if you see 2 liberties, just stop.)
                if liberties == 2:
                    return liberties

        return liberties

    # a stone was just placed at |pt|, of color |color|;
    # do any captures that result from this.
    def __do_captures(self, point, color):
        # reset last_captures
        self.last_captures = 0

        # ASSUME this is a legal move.  every chain with 0 liberties,
        # except for the one containing pt, should be removed.  the
        # only 4 chains i need to check are the 4 touching this stone.

        # is there an enemy stone in each of these directions?  and if
        # so, does its chain have 0 liberties now?  then kill it.

        for pt in point.all4(self.size):
            if self.get(pt)==opposite(color) and self.__count_liberties(pt)==0:
                self.__kill(pt)

        # suicides: if, after possibly killing my new neighbors, this
        # new chain has no liberties, kill it
        if self.__count_liberties(point)==0:
            self.__kill(point)

    # kill all of the stones in the group which contains the point |target|.
    # (runs in O(size^2) time.)
    def __kill(self, target):
        # target id to kill
        chain_id = self.chain[target.col][target.row]

        num_killed = self.__rename(chain_id, 0)
        if chain_id > 0:
            self.black_prisoners += num_killed
        else:
            self.white_prisoners += num_killed

        self.last_captures += num_killed

    # replace all points with id=old with id=new;
    # return the number of points that were changed.
    # (used by: kill() for killing, and place_stone() for merging.)
    def __rename(self, old, new):
        num_changed = 0
        for i in range(self.size):
            for j in range(self.size):
                if self.chain[i][j] == old: # CHECK: is there an easier way to do this in python?
                    self.chain[i][j] = new
                    num_changed += 1
        return num_changed

    # place a stone, deal with captures, and update last_stone,
    # markers, turn.
    def play_stone(self, point, color):
        self.last_stone = point

        # play the stone -- white stones negative, black stones positive
        if color == WHITE:
            new_chain = -self.next_chain
        else:
            new_chain = self.next_chain
        self.chain[point.col][point.row] = new_chain
        self.next_chain += 1

        # join all of my chains.
        # for each chain touching this, which is my color, set that chain to my new id.
        for pt in point.all4(self.size):
            if self.get(pt)==color:
                old = self.chain[pt.col][pt.row]
                new = self.chain[point.col][point.row]

                self.__rename(old, new)

        # take care of captures
        self.__do_captures(point, color)

        # update other things...
        self.turn = opposite(color)
        self.markers = []

    def play_pass(self): # ("pass" means something else in python!)
        self.last_stone = None
        self.turn = opposite(self.turn)
        self.markers = []

    def erase(self, point):
        # you'd never do this, of course, but SGF FF[4] has it (gah...)

        print "WRITEME: delete point %s" % point
        # unfortunately, with the data structure i'm using, this is rather hard...
